// 默认1为根，边数建多少传多少，注意无向边要*2
struct LCA {
	struct Edge {
		int to, nxt;
	};

	LCA(int n, int m) : head_(n + 1), dep_(n + 1), log_(n * 2 + 1), 
											fa_(n * 2 + 5), q_(n * 2 + 1), dfn_(n * 2 + 1), 
											e_(m + 1), idx_(0), tot_(0) {}

	void add_edge(int u, int v) {
		e_[++tot_] = (Edge){v, head_[u]};
    head_[u] = tot_;
	}

	void dfs(int u, int pa) {
		dfn_[u] = ++idx_;
		q_[idx_] = u;
    dep_[u] = dep_[pa] + 1;
    for(int i = head_[u]; i; i = e_[i].nxt){
      int v = e_[i].to;
      if(v != pa) {
        dfs(v, u);
        q_[++idx_] = u;
      }
    }
	}

	void build() {
		dfs(1, 0);
		log_[0] = -1;
		int m = 31 - __builtin_clz(idx_);
    for (int i = 1; i <= idx_; i++) {
      log_[i] = log_[i >> 1] + 1;
      fa_[i].resize(m + 1);
			fa_[i][0] = q_[i];
		}
		for (int j = 1; j <= m; j++) {
      int offset = 1 << (j - 1);
      for(int i = 1; i + offset <= idx_; ++i){
          int f1 = fa_[i][j - 1], f2 = fa_[i + offset][j - 1];
          fa_[i][j] = dep_[f1] < dep_[f2] ? f1 : f2;
      }
    }
	}

	void work() {
		idx_ = 0;
		build();	
	}

	int get_lca(int u, int v) {
		if(dfn_[u] > dfn_[v]) {
			swap(u,v);
    }
    u = dfn_[u], v = dfn_[v];
    int kk = log_[v - u + 1], f1 = fa_[u][kk], f2 = fa_[v- (1 << kk) + 1][kk];
    return dep_[f1] < dep_[f2] ? f1 : f2;
	}

	int idx_, tot_;
	vector<int> head_, dep_, log_, dfn_, q_;
	vector<vector<int>> fa_;
	vector<Edge> e_;
};